package 搜索.BFS;

import java.util.*;

/*
解题思路：
    这题求最短转换序列的长度，当然用BFS。这题难点有2.
    ①画出无向图 ②根据什么条件找到邻居节点

    我之前想到一种方法是用beginword和wordlist中的每一个字符串相比较，如果只有一个字符不同那么beginword和它之间就有连线，
    同理beginword的邻居节点的邻居节点也用这个方法求。但是这样做有问题，当wordlist一大了之后就会超出时间限制。
    所以换一个思路，用一个Hash表把所有的单词列表放进一个哈希表中，借助哈希表【复杂度是O(26×wordLen)】，找到邻居与 N 【这里 N 是单词列表的长度】无关，所以不会超时

    例如beginword是“hit”，我们一开始只要用a-z替换hit的h，看hash表是否有符合的，如果没有，再用a-z替换i，以此类推



 */
public class 单词接龙_127 {


    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        List<String> visited = new ArrayList<>();


        Set<String> wordSet = new HashSet<>(wordList);//把wordList放入Hash表中，用来比较遍历，如果直接和wordlist来比较会超时
        if (!wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);

        queue.add(beginWord);
        visited.add(beginWord);
        int step = 0;

        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            while (size-- > 0) {
                String poll = queue.poll();

                // 如果 poll 能够修改 1 个字符与 endWord 相同，证明它俩有连线，走出那一步即可，即返回 step + 1(走出的那一步)
                char[] charArray = poll.toCharArray();//把当前字符串拆成字符数组，便于替换
                for (int i = 0; i < endWord.length(); i++) {
                    // 先保存，然后恢复，即一轮后要重置该字符串
                    char originChar = charArray[i];//因为每次只能替换一个字符，所以要保存一个原本。
                    for (char k = 'a'; k <= 'z'; k++) {//遍历a-z
                        if (k == originChar) {//即Hash表中遇到了和beginword一样的字符串，直接跳过
                            continue;
                        }
                        charArray[i] = k;//替换一个字符
                        String nextWord = String.valueOf(charArray);//替换后的字符串
                        if (wordSet.contains(nextWord)) {//即  beginword和hash表中的某字符串只有一个字符不同，它们之间生成连线
                            if (nextWord.equals(endWord)) {//符合条件，直接返回
                                return step + 1;//因为nextWord.equals(endWord)只是找到了它和endword之间有连线，还没有迈出那一步，需要迈出那一步才能到endword
                            }
                            if (!visited.contains(nextWord)) {//找它的邻居节点
                                queue.add(nextWord);
                                // 注意：添加到队列以后，必须马上标记为已经访问
                                visited.add(nextWord);
                            }
                        }
                    }
                    // 恢复
                    charArray[i] = originChar;
                }


            }

        }
        return 0;
    }


//    public int FindDiff(String beginWord, String target) {
//        int length = beginWord.length();//因为所有单词具有相同的长度。所以只要定义一个length就行
//        int diff = 0;
//        char[] b = beginWord.toCharArray();
//        char[] t = target.toCharArray();
//        for (int i = 0; i < length; i++) {
//            if (b[i] == t[i]) {
//                diff++;
//            }
//
//        }
//        return diff;
//    }

}
